#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct {
    int *data;
    int len;
    int capacity;
} Stack;

void init(Stack *s)
{
    s->len = 0;
    s->capacity = 256;
    s->data = (int *) malloc(s->capacity * sizeof(s->data[0]));
}

void destroy(Stack *s)
{
    s->len = 0;
    free(s->data);
}

void push(Stack *s, int a)
{
    if (s->len == s->capacity) {
        int *tmp = (int *) malloc(2 * s->capacity * sizeof(s->data[0]));
        memcpy(tmp, s->data, s->capacity * sizeof(s->data[0]));
        free(s->data);
        s->data = tmp;
        s->capacity *= 2;
    }

    s->data[s->len] = a;
    s->len++;
}

int pop(Stack *s)
{
    if (s->len == 0) {
        return 0;
    }

    s->len--;
    return s->data[s->len];
}

bool is_op(char *str)
{
    return strcmp(str, "+") == 0 || strcmp(str, "-") == 0 || strcmp(str, "*") == 0 || strcmp(str, "/") == 0;
}

int calc(int a, int b, char op)
{
    switch (op) {
        case '+':
            return a + b;
        case '-':
            return a - b;
        case '*':
            return a * b;
        case '/':
            return a / b;
        default:
            return 0;
    }
}

void show(Stack *s)
{
    for (int i = 0; i < s->len; i++) {
        printf("%d%c", s->data[i], i == s->len - 1 ? '\n' : ' ');
    }
}

int evalRPN(char **tokens, int tokensSize)
{
    Stack s;
    init(&s);

    for (int i = 0; i < tokensSize; i++) {
        if (is_op(tokens[i])) {
            int a = pop(&s);
            int b = pop(&s);
            push(&s, calc(b, a, tokens[i][0]));
        } else {
            push(&s, atoi(tokens[i]));
        }
        // show(&s);
    }

    int result = pop(&s);
    destroy(&s);

    return result;
}

int main(int argc, char const *argv[])
{
    char *s[] = { "10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+" };
    int r = evalRPN(s, sizeof(s) / sizeof(s[0]));
    printf("%d\n", r);
    return 0;
}
